package com.wcj.string;

public class KMP {

    public static void main(String[] args) {
        String str = "ACTGPACY";
        String mainStr = "ACTGPACTGKACTGPACY";
        int[] ints = buildNext(str);
        for (int anInt : ints) {
            System.out.print(anInt);
        }

        int match = match(str, mainStr);
        System.out.println(match);

    }


    public static int match (String P, String S){ // KMP 算法
        int[] next = buildNext(P); // 构造 next 表
        int m = S.length(), i = 0; // 文本串指针
        int n = P.length(), j = 0; //模式串指针
        while (j < n && i < m) // 自左向右逐个比对字符
            if (0 > j || S.charAt(i) == P.charAt(j)) // 若匹配，或 P 已移除最左侧
            {i++; j++;} // 则转到下一字符
            else
                j = next[j]; // 模式串右移（注意：文本串不用回退）
        if (i != m && j != n){
            return i - j;
        }else
            return -1;

    }

    public static int[] buildNext(String P) { // 构造模式串 P 的 next 表
        int len = P.length(), j = 0; // “主”串指针
        int[] N = new int[len]; // next 表
        int t = N[0] = -1; // 模式串指针
        while (j < len - 1)
            if ( 0 > t || P.charAt(j) == P.charAt(t)){ // 匹配
                j++; t++;
                N[j] = t; // 此句可改进为 N[j] = (P[j] != P[t] ? t : N[t]);
            }else // 失配
                t = N[t];
        return N;
    }

    /**
     * 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。
     * @param haystack
     * @param needle
     * @return
     */
    public static int strStr(String haystack, String needle) {
        int[] next = buildNext(needle); // 构造 next 表
        int m = haystack.length(), i = 0; // 文本串指针
        int n = needle.length(), j = 0; //模式串指针
        while (j < n && i < m) // 自左向右逐个比对字符
            if (0 > j || haystack.charAt(i) == needle.charAt(j)) // 若匹配，或 P 已移除最左侧
            {i++; j++;} // 则转到下一字符
            else
                j = next[j]; // 模式串右移（注意：文本串不用回退）
        if (i != m || i==m&&j==n){
            return i - j;
        }
        else return -1;
    }

    int F[];
    void PrefixTable(char P[]){
        int i = 1;
        int j = 0;
        F[0] = 0;
        while (i < P.length){
            if (P[i] == P[j]){
                F[i] = j + 1;
                i++;
                j++;
            }else if (j > 0){
                j = F[j - 1];
            }else {
                F[i] = 0;
                i++;
            }
        }
    }

    int KMP(char T[],char P[]){
        int i = 0;
        int j = 0;
        PrefixTable(P);
        while (i < T.length){
            if (T[i] == P[j]){
                if (j == P.length - 1){
                    return i - j;
                }else {
                    i++;
                    j++;
                }
            }else if (j > 0){
                j = F[j - 1];
            }else {
                i++;
            }
        }
        return -1;
    }

}
